{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count the Number of Good Subsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #math #string #combinatorics #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #数学 #字符串 #组合数学 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countGoodSubsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #好子序列的个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果字符串的某个 <strong>子序列</strong> 不为空，且其中每一个字符出现的频率都相同，就认为该子序列是一个好子序列。</p>\n",
    "\n",
    "<p>给你一个字符串&nbsp;<code>s</code> ，请你统计并返回它的好子序列的个数。由于答案的值可能非常大，请返回对 <code>10<sup>9</sup> + 7</code> 取余的结果作为答案。</p>\n",
    "\n",
    "<p>字符串的 <strong>子序列</strong> 是指，通过删除一些（也可以不删除）字符且不改变剩余字符相对位置所组成的新字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aabb\"\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>s 的子序列的总数为 <code>2<sup>4 </sup>= 16 。其中，有 5 个子序列不是好子序列，分别是 </code>\"<em><strong>aab</strong></em>b\"，\"a<em><strong>abb</strong></em>\"，\"<strong><em>a</em></strong>a<em><strong>bb</strong></em>\"，\"<em><strong>aa</strong></em>b<em><strong>b</strong></em>\" 以及空字符串。因此，好子序列的个数为 16 <code>- 5 = 11</code> 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"leet\"\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>s 的子序列的总数为 <code>2<sup>4 </sup>= 16 。</code>其中，<code>有 4 个子序列不是好子序列，分别是 </code>\"<em><strong>lee</strong></em>t\"，\"l<em><strong>eet</strong></em>\"，\"<em><strong>leet</strong></em>\" 以及空字符串。因此，好子序列的个数为 16 <code>- 4 = 12</code> 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcd\"\n",
    "<strong>输出：</strong>15\n",
    "<strong>解释：</strong>s 所有非空子序列均为好子序列。因此，好子序列的个数为 16<code> - 1 = 15</code> 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-the-number-of-good-subsequences](https://leetcode.cn/problems/count-the-number-of-good-subsequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-the-number-of-good-subsequences](https://leetcode.cn/problems/count-the-number-of-good-subsequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aabb\"', '\"leet\"', '\"abcd\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAX_N, MOD = int(1e4) + 5, int(1e9) + 7\n",
    "fact, infact = [0] * MAX_N, [0] * MAX_N\n",
    "fact[0] = infact[0] = 1\n",
    "# 算出 i 的阶乘及阶乘逆元\n",
    "for i in range(1, MAX_N):\n",
    "    fact[i] = fact[i - 1] * i % MOD\n",
    "    # i 与 MOD 互质，且 MOD 为质数\n",
    "    infact[i] = infact[i - 1] * pow(i, MOD - 2, MOD) % MOD\n",
    "\n",
    "class Solution:\n",
    "    def countGoodSubsequences(self, s: str) -> int:\n",
    "        my_comb = lambda a, b: fact[a] * infact[b] % MOD * infact[a - b] % MOD\n",
    "        freq, res = 1, 0\n",
    "        log = Counter(s)\n",
    "        while log:\n",
    "            cur = 1\n",
    "            for k, v in list(log.items()):\n",
    "                cur *= my_comb(v, freq) + 1\n",
    "                if v == freq: del log[k]\n",
    "            res = (res + cur - 1) % MOD\n",
    "            freq += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 排列组合\n",
    "# 预处理阶乘及其逆元\n",
    "fac = [1 for _ in range(10001)]\n",
    "rev = [1 for _ in range(10001)]\n",
    "mod = 10 ** 9 + 7\n",
    "for i in range(1, 10001):\n",
    "    fac[i] = fac[i - 1] * i % mod\n",
    "    rev[i] = pow(fac[i], mod - 2, mod)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def comb(self,n,m):\n",
    "        if n < m:\n",
    "            return 0\n",
    "\n",
    "        return fac[n] * rev[m] * rev[n - m] % mod\n",
    "\n",
    "\n",
    "    def countGoodSubsequences(self, s: str) -> int:\n",
    "        cnt = [0 for _ in range(26)]\n",
    "        for c in s:\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "\n",
    "        maxv = max(cnt)\n",
    "        ans = 0\n",
    "        for i in range(1, maxv + 1):\n",
    "            cur = 1\n",
    "            for j in range(26):\n",
    "                cur *= self.comb(cnt[j], i) + 1\n",
    "                cur %= mod\n",
    "\n",
    "            # 好序列非空\n",
    "            cur -= 1\n",
    "            ans += cur\n",
    "            ans %= mod\n",
    "\n",
    "        return ans      \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#这题的思路很有意思，我的思路是对于长度为len的子序列，找到每一个j，满足len%j=0\n",
    "#表示要找到len/j个字符，每个字符出现的次数大于等于j，假设有k个满足要求的。\n",
    "#然后在k个字符中选len/j个字符，每个字符计算cp(j,cnt[i])，然后乘起来，在加总所有的选法\n",
    "#这样问题就变得非常复杂，每个字符的cnt不一样。\n",
    "\n",
    "#大佬们的做法是，每个字符选i个，对于每一个字符c，如果cnt[c]<i，就跳过，否则\n",
    "#要么选，有cp(i,cnt[c])种方法，要么不选有1种方法，所以c贡献了cp+1种\n",
    "#对于每一个cnt[c]>=i的，把他们的(cp+1)都乘起来就是总的方案。\n",
    "#特殊的情况是每一个字符都不选，就是空串，最后总数-1\n",
    "#这是一种动态规划的方案，选和不选\n",
    "fact = [1]*20001 #利用python的负数下标，把阶乘本身和逆元放在同一个数组\n",
    "mod = 10**9+7\n",
    "for j in range(2,10001):\n",
    "    fact[j]=fact[j-1]*j%mod\n",
    "    fact[-j]=pow(fact[j],mod-2,mod) # 理解不了的真心建议死记吧，我也不敢说下次会在啥时候出了\n",
    "\n",
    "class Solution:\n",
    "    def countGoodSubsequences(self, s: str) -> int:\n",
    "\n",
    "        table = defaultdict(int)   #用哈希表计数，这样每种频率就不一定会循环26次了\n",
    "        for ch in s:\n",
    "            table[ch]+=1\n",
    "        \n",
    "        def cbo(n,m):\n",
    "            if n<m: return 0 #n<m为非法，这种字母必须放弃\n",
    "            return fact[n]*fact[-m]*fact[m-n]%mod #分母的部分为逆元，对应fact数组里的负数下标\n",
    "\n",
    "        vs = list(table.values())\n",
    "        mx = max(vs) \n",
    "        ans = 0\n",
    "\n",
    "        for p in range(1,mx+1): # 枚举每种频率\n",
    "            cur = 1\n",
    "            for v in vs: #枚举每种字母\n",
    "                cur*= cbo(v,p)+1 \n",
    "                cur%=mod\n",
    "            ans+=cur-1 #注意排除空序列\n",
    "            ans%=mod\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# 预处理阶乘及其逆元\n",
    "fac = [1 for _ in range(10001)]\n",
    "rev = [1 for _ in range(10001)]\n",
    "mod = 10 ** 9 + 7\n",
    "for i in range(1,10001):\n",
    "    fac[i] = fac[i - 1] * i % mod\n",
    "    rev[i] = pow(fac[i],mod - 2,mod)\n",
    "\n",
    "class Solution:\n",
    "    def comb(self,n,m):\n",
    "        if n < m:\n",
    "            return 0\n",
    "        return fac[n] * rev[m] * rev[n - m] % mod\n",
    "\n",
    "    def countGoodSubsequences(self, s: str) -> int:\n",
    "        cnt = [0 for _ in range(26)]\n",
    "        for c in s:\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "        maxv = max(cnt)\n",
    "        ans = 0\n",
    "        for i in range(1,maxv + 1):\n",
    "            cur = 1\n",
    "            for j in range(26):\n",
    "                cur *= self.comb(cnt[j],i) + 1\n",
    "                cur %= mod\n",
    "\n",
    "            # 好序列非空\n",
    "            cur -= 1\n",
    "            ans += cur\n",
    "            ans %= mod\n",
    "\n",
    "        return ans      \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "fac = [1 for _ in range(10001)]\n",
    "rev = [1 for _ in range(10001)]\n",
    "mod = 10 ** 9 + 7\n",
    "for i in range(1,10001):\n",
    "    fac[i] = fac[i - 1] * i % mod\n",
    "    rev[i] = pow(fac[i],mod - 2,mod)\n",
    "\n",
    "class Solution:\n",
    "    def countGoodSubsequences(self, s: str) -> int:\n",
    "        def comb(n,m):\n",
    "            if n < m:\n",
    "                return 0\n",
    "            return fac[n] * rev[m] * rev[n - m]\n",
    "\n",
    "        cnt = [0 for _ in range(26)]\n",
    "        for c in s:\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "        maxv = max(cnt)\n",
    "        mod = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        for i in range(1,maxv + 1):\n",
    "            v = 1\n",
    "            for j in range(26):\n",
    "                v *= comb(cnt[j],i) % mod + 1\n",
    "                v %= mod\n",
    "            v -= 1\n",
    "            v %= mod\n",
    "            ans += v\n",
    "            ans %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "fact = [1]*20001 #利用python的负数下标，把阶乘本身和逆元放在同一个数组\r\n",
    "mod = 10**9+7\r\n",
    "for j in range(2,10001):\r\n",
    "    fact[j]=fact[j-1]*j%mod\r\n",
    "    fact[-j]=pow(fact[j],mod-2,mod) # 理解不了的真心建议死记吧，我也不敢说下次会在啥时候出了\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def countGoodSubsequences(self, s: str) -> int:\r\n",
    "\r\n",
    "        table = defaultdict(int)   #用哈希表计数，这样每种频率就不一定会循环26次了\r\n",
    "        for ch in s:\r\n",
    "            table[ch]+=1\r\n",
    "        \r\n",
    "        def cbo(n,m):\r\n",
    "            if n<m: return 0 #n<m为非法，这种字母必须放弃\r\n",
    "            return fact[n]*fact[-m]*fact[m-n]%mod #分母的部分为逆元，对应fact数组里的负数下标\r\n",
    "\r\n",
    "        vs = list(table.values())\r\n",
    "        mx = max(vs) \r\n",
    "        ans = 0\r\n",
    "\r\n",
    "        for p in range(1,mx+1): # 枚举每种频率\r\n",
    "            cur = 1\r\n",
    "            for v in vs: #枚举每种字母\r\n",
    "                cur*= cbo(v,p)+1 \r\n",
    "                cur%=mod\r\n",
    "            ans+=cur-1 #注意排除空序列\r\n",
    "            ans%=mod\r\n",
    "        \r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "fact = [1] * 20001\n",
    "mod = 10 ** 9 + 7\n",
    "\n",
    "for i in range(2, 10001):\n",
    "    fact[i] = fact[i - 1] * i % mod\n",
    "    fact[-i] = pow(fact[i], mod - 2, mod)\n",
    "\n",
    "class Solution:\n",
    "    def countGoodSubsequences(self, s: str) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for c in s:\n",
    "            cnt[c] += 1\n",
    "\n",
    "        vs = list(cnt.values())\n",
    "        mx = max(vs)\n",
    "        ans = 0\n",
    "\n",
    "        for p in range(1, mx + 1):\n",
    "            cur = 1\n",
    "            for v in vs:\n",
    "                cur = cur * (self.comb(v, p) + 1) % mod\n",
    "            ans = (ans + cur - 1) % mod\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def comb(self, n, m):\n",
    "        if n < m:\n",
    "            return 0\n",
    "        return fact[n] * fact[-m] * fact[m - n] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 排列组合\n",
    "# 预处理阶乘及其逆元\n",
    "fac = [1 for _ in range(10001)]\n",
    "rev = [1 for _ in range(10001)]\n",
    "mod = 10 ** 9 + 7\n",
    "for i in range(1, 10001):\n",
    "    fac[i] = fac[i - 1] * i % mod\n",
    "    rev[i] = pow(fac[i], -1, mod)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def comb(self, n, m):\n",
    "        if n < m:\n",
    "            return 0\n",
    "\n",
    "        return fac[n] * rev[m] * rev[n - m] % mod\n",
    "\n",
    "\n",
    "    def countGoodSubsequences(self, s: str) -> int:\n",
    "        cnt = [0 for _ in range(26)]\n",
    "        for c in s:\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "\n",
    "        maxv = max(cnt)\n",
    "        ans = 0\n",
    "        for i in range(1, maxv + 1):\n",
    "            cur = 1\n",
    "            for j in range(26):\n",
    "                cur *= self.comb(cnt[j], i) + 1\n",
    "                cur %= mod\n",
    "\n",
    "            # 好序列非空\n",
    "            cur -= 1\n",
    "            ans += cur\n",
    "            ans %= mod\n",
    "\n",
    "        return ans      \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 排列组合\n",
    "# 预处理阶乘及其逆元\n",
    "fac = [1 for _ in range(10001)]\n",
    "rev = [1 for _ in range(10001)]\n",
    "mod = 10 ** 9 + 7\n",
    "for i in range(1, 10001):\n",
    "    fac[i] = fac[i - 1] * i % mod\n",
    "    rev[i] = pow(fac[i], -1, mod)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def comb(self, n, m):\n",
    "        if n < m:\n",
    "            return 0\n",
    "\n",
    "        return fac[n] * rev[m] * rev[n - m] % mod\n",
    "\n",
    "\n",
    "    def countGoodSubsequences(self, s: str) -> int:\n",
    "        cnt = [0 for _ in range(26)]\n",
    "        for c in s:\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "\n",
    "        maxv = max(cnt)\n",
    "        ans = 0\n",
    "        for i in range(1, maxv + 1):\n",
    "            cur = 1\n",
    "            for j in range(26):\n",
    "                cur *= self.comb(cnt[j], i) + 1\n",
    "                cur %= mod\n",
    "\n",
    "            # 好序列非空\n",
    "            cur -= 1\n",
    "            ans += cur\n",
    "            ans %= mod\n",
    "\n",
    "        return ans      \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "# 预处理阶乘及其逆元\n",
    "fac = [1 for _ in range(10001)]\n",
    "rev = [1 for _ in range(10001)]\n",
    "mod = 10 ** 9 + 7\n",
    "for i in range(1,10001):\n",
    "    fac[i] = fac[i - 1] * i % mod\n",
    "    rev[i] = pow(fac[i],mod - 2,mod)\n",
    "\n",
    "def comb(n, m):\n",
    "    if n < m:\n",
    "        return 0\n",
    "    return fac[n] * rev[m] * rev[n - m] % mod\n",
    "\n",
    "class Solution:\n",
    "    def countGoodSubsequences(self, s: str) -> int:\n",
    "        cnt = [0 for _ in range(26)]\n",
    "        for c in s:\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "        maxv = max(cnt)\n",
    "        ans = 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for i in range(1,maxv + 1):\n",
    "            cur = 1\n",
    "            for j in range(26):\n",
    "                cur *= comb(cnt[j], i) + 1\n",
    "                cur %= MOD\n",
    "            # 好序列非空\n",
    "            cur -= 1\n",
    "            ans += cur\n",
    "            ans %= MOD\n",
    "        return ans      \n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
